package es.ull.etsii.aa.metodos;

 // Permute.java -- A class generating all permutations
 
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.lang.reflect.Array;
 
public class Permute implements Iterator {
 
	private final int size;
	private final LinkedList<Object> elements;  // copy of original 0 .. size-1
	private LinkedList<Object> ar;           // array for output,  0 .. size-1
	private final LinkedList<Integer> permutation;  // perm of nums 1..size, perm[0]=0
 
    private boolean next = true;
 
    // int[], double[] array won't work :-(
	public Permute (LinkedList<Object> e) {
		size = e.size();
		elements = new LinkedList<Object>(e);    	// size // not suitable for primitives
		ar = new LinkedList<Object>(e);
		permutation = new LinkedList<Integer>();			// size + 1
		for (int i=0; i<size+1; i++) {
			permutation.add(i);				// permutation [i]=i;
		}
	}
   
	private void formNextPermutation () {
		ar = new LinkedList<Object>(elements);
		for (int i=0; i<size; i++) {
	      // i+1 because perm[0] always = 0
	  // perm[]-1 because the numbers 1..size are being permuted
	          ar.set(i, elements.get(permutation.get(i+1)-1));
	    }
	}
	 
    public boolean hasNext() {
       return next;
    }
 
    public void remove() throws UnsupportedOperationException {
       throw new UnsupportedOperationException();
    }
 
    private void swap (final int i, final int j) {
       Collections.swap(permutation, i, j);
    }
 
    // does not throw NoSuchElement; it wraps around!
    public Object next() throws NoSuchElementException {
 
       formNextPermutation ();  // copy original elements
 
       int i = size-1;
       while (permutation.get(i)>permutation.get(i+1)) i--;
 
       if (i==0) {
          next = false;
          for (int j=0; j<size+1; j++) {
             permutation.set(j, j);
          }
          return ar;
       }
 
       int j = size;
       
       while (permutation.get(i) > permutation.get(j)) j--;
       swap (i,j);
       int r = size;
       int s = i+1;
       while (r>s) { swap(r,s); r--; s++; }
 
       return ar;
    }
 
    public String toString () {
    	final int n = ar.size();
    	final StringBuffer sb = new StringBuffer ("[");
    	for (int j=0; j<n; j++) {
    		sb.append (ar.get(j).toString());
	    		if (j<n-1) sb.append (",");
    	}
    	sb.append("]");
    	return new String (sb);
    }
 
 }